Test Series - Data Structure

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

Test Number 110/115

Q: Incidence matrix and Adjacency matrix of a graph will always have same dimensions?
A. True
B. False
C. ..
D. ..
Solution: For a graph having V vertices and E edges, Adjacency matrix have V*V elements while Incidence matrix have V*E elements.
Q: The column sum in an incidence matrix for a simple graph is __________
A. depends on number of edges
B. always greater than 2
C. equal to 2
D. equal to the number of edges
Solution: For every edge only the vertices with which it is connected would have the value 1 in the matrix, as an edge connects two vertices sum will always be 2.
Q: What are the dimensions of an incidence matrix?
A. Number of edges*number of edges
B. Number of edges*number of vertices
C. Number of vertices*number of vertices
D. Number of edges * (1⁄2 * number of vertices)
Solution: Columns may represent edges and vertices may be represented by the rows.
Q: The column sum in an incidence matrix for a directed graph having no self loop is __________
A. 0
B. 1
C. 2
D. 0
Solution: Under every edge column there would be either all 0 values or a pair of -1 and +1 value exists.
Q: Time complexity to check if an edge exists between two vertices would be ___________
A. O(V*V)
B. O(V+E)
C. O(1)
D. O(E)
Solution: We have to check for all edges, in the worst case the vertices will have no common edge.
Q: The graphs G1 and G2 with their incidences matrices given are Isomorphic.

		e1 	e2 	e3 	e4 	e5 	e6
	v1	1	0	0	0	0	0
	v2	1	1	0	0	0	1
	v3	0	1	1	0	1	0
	v4	0	0	1	1	0	0
	v5	0	0	0	1	1	1
 
 
 
		e1 	e2 	e3 	e4 	e5 	e6
	v1	0	0	1	0	0	0
	v2	1	0	1	0	1	0
	v3	1	1	0	1	0	0
	v4	0	1	0	0	0	1
	v5	0	0	0	1	1	1
A. True
B. False
C. 
D. 
Solution: Two graphs are isomorphic if their Incidence Matrices differ only by permutation of columns and rows.
Q: If a connected Graph (G) contains n vertices what would be the rank of its incidence matrix?
A. n-1
B. values greater than n are possible
C. values less than n-1 are possible
D. insufficient Information is given
Solution: Every column of the incidence matrix may contain only +1 and -1 as non zero entries rank would be less than n.
Q: A Graph Structured Stack is a _____________
A. Undirected Graph
B. Directed Graph
C. Directed Acyclic Graph
D. Regular Graph
Solution: A Graph Structured Stack is a Directed Acyclic Graph with each path representing a stack.
Q: If a Graph Structured Stack contains {1,2,3,4} {1,5,3,4} {1,6,7,4} and {8,9,7,4}, what would be the source and sink vertices of the DAC?
A. Source – 1, 8 Sink – 7,4
B. Source – 1 Sink – 8,4
C. Source – 1, 8 Sink – 4
D. Source – 4, Sink – 1,8
Solution: Every Stack of the Graph Structured Stack represents a path, each path starts with the source vertex and ends with the sink vertex.
Q: Graph Structured Stack finds its application in _____________
A. Bogo Sort
B. Tomita’s Algorithm
C. Todd–Coxeter algorithm
D. Heap Sort
Solution: Tomita’s is a parsing algorithm which uses Graph Structured Stack in its implementation.

You Have Score    /10